import java.util.HashMap;
import java.util.LinkedList;

public class DeepestLeavesSum {

    public int deepestLeavesSum(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int curLevel = 1;
        int count = 0;
        HashMap<TreeNode, Integer> map = new HashMap<>();
        map.put(root, 1);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            int nodeLevel = map.get(poll);
            if (curLevel != nodeLevel) {
                curLevel++;
                count = poll.val;
            } else {
                count += poll.val;
            }
            if (poll.left != null) {
                map.put(poll.left, curLevel + 1);
                queue.add(poll.left);
            }
            if (poll.right != null) {
                map.put(poll.right, curLevel + 1);
                queue.add(poll.right);
            }
        }
        return count;
    }
}
